package com.hss.interview;


public class ListReverse {

    public static class Node {
        public int value;
        public Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {

        Node note5 = new Node(5, null);
        Node note4 = new Node(4, note5);
        Node note3 = new Node(3, note4);
        Node note2 = new Node(2, note3);
        Node note1 = new Node(1, note2);
//        reverse(note1);
        reverse2(note1);
        print(note5);

    }

    public static void print(Node head) {
        while (head != null) {
            System.out.println(head.value);
            head = head.next;
        }
    }

    /**
     * 迭代方式
     */
    public static void reverse(Node head) {
        Node cur = head, next = null, pre = null;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;

        }
    }

    public static void reverse2(Node head) {
       Node p =head;
       if (p.next ==null){
           return;
       }

       head = p.next;
       reverse2(head);
       p.next.next = p;
       p.next = null;

    }

    public static Node findTail(Node head){
        Node tail = head;
        while (head !=null && head.next !=null){
            tail = head;
            head = head.next;
        }
        return tail;
    }
}